In [1]:
"""
Modified from: http://hubpages.com/technology/Simplex-Algorithm-in-Python
"""
from __future__ import division
from numpy import *
# Ref: http://stackoverflow.com/questions/23344185/how-to-convert-a-decimal-number-into-fraction
from fractions import Fraction
class Tableau:
def __init__(self, obj):
self.obj = [1] + obj
self.rows = []
self.cons = []
self.no_variables = len(obj)
self.no_constraints = 0
self.is_fraction = False # set True to output in fraction
def add_constraint(self, expression, value):
self.rows.append([0] + expression)
self.cons.append(value)
self.no_constraints += 1
self.header_tableau = ["Basic"] + ["x"+str(i+1) for i in range(self.no_variables)] \
+ ["s"+str(i+1) for i in range(self.no_constraints)] \
+ ["Solution"]
self.basic_variables = ["s"+str(i+1) for i in range(self.no_constraints)]
def _pivot_column(self):
low = 0
idx = 0
for i in range(1, len(self.obj)-1):
if self.obj[i] < low:
low = self.obj[i]
idx = i
if idx == 0: return -1
return idx
def _pivot_row(self, col):
rhs = [self.rows[i][-1] for i in range(len(self.rows))]
lhs = [self.rows[i][col] for i in range(len(self.rows))]
ratio = []
for i in range(len(rhs)):
if lhs[i] == 0:
ratio.append(99999999 * abs(max(rhs)))
continue
ratio.append(rhs[i]/lhs[i])
return argmin(ratio)
def display(self):
if self.is_fraction:
# Formatting the output in fraction
# Ref: https://pyformat.info/
fmt = '{:<8}'.format("Basic") \
+ "".join(['{:>8}'.format("x"+str(i+1)) for i in range(self.no_variables)]) \
+ "".join(['{:>8}'.format("s"+str(i+1)) for i in range(self.no_constraints)]) \
+ '{:>8}'.format("Sol.")
fmt += "\n"
fmt += '{:<8}'.format("z") \
+ "".join(["{:>8}".format(Fraction(item).limit_denominator(3)) for item in self.obj[1:]])
for i, row in enumerate(self.rows):
fmt += "\n"
fmt += '{:<8}'.format(self.basic_variables[i]) \
+ "".join(["{:>8}".format(Fraction(item).limit_denominator(3)) for item in row[1:]])
print fmt
else:
# Formatting the output in float with 2 decimal places
fmt = '{:<8}'.format("Basic") \
+ "".join(['{:>8}'.format("x"+str(i+1)) for i in range(self.no_variables)]) \
+ "".join(['{:>8}'.format("s"+str(i+1)) for i in range(self.no_constraints)]) \
+ '{:>8}'.format("Sol.")
fmt += "\n"
fmt += '{:<8}'.format("z") + "".join(["{:>8.2f}".format(item) for item in self.obj[1:]])
for i, row in enumerate(self.rows):
fmt += "\n"
fmt += '{:<8}'.format(self.basic_variables[i]) \
+ "".join(["{:>8.2f}".format(item) for item in row[1:]])
print fmt
# print '\n', matrix([self.obj] + self.rows)
def _pivot(self, row, col):
e = self.rows[row][col]
self.rows[row] /= e
for r in range(len(self.rows)):
if r == row: continue
self.rows[r] = self.rows[r] - self.rows[r][col]*self.rows[row]
self.obj = self.obj - self.obj[col]*self.rows[row]
def _check(self):
if min(self.obj[1:-1]) >= 0: return 1
return 0
def solve(self):
# build full tableau
for i in range(len(self.rows)):
self.obj += [0]
ident = [0 for r in range(len(self.rows))]
ident[i] = 1
self.rows[i] += ident + [self.cons[i]]
self.rows[i] = array(self.rows[i], dtype=float)
self.obj = array(self.obj + [0], dtype=float)
# solve
self.display()
while not self._check():
c = self._pivot_column()
r = self._pivot_row(c)
self._pivot(r,c)
# print '\npivot column: %s\npivot row: %s'%(c+1,r+2)
print '\n'
print 'Entering Variable: ', self.header_tableau[c]
print 'Leaving Variable : ', self.basic_variables[r]
print '\n'
# Updating the basic variable
for index, item in enumerate(self.basic_variables):
if self.basic_variables[index] == self.basic_variables[r]:
self.basic_variables[index] = self.header_tableau[c]
self.display()
if __name__ == '__main__':
"""
max z = 2x + 3y + 2z
st
2x + y + z <= 4
x + 2y + z <= 7
z <= 5
x,y,z >= 0
"""
t = Tableau([-2,-3,-2])
t.add_constraint([2, 1, 1], 4)
t.add_constraint([1, 2, 1], 7)
t.add_constraint([0, 0, 1], 5)
t.is_fraction = True
t.solve()
Solve the following problem: $$ \left.\begin{array}{rrcl} \max & 3x+2y+5z \\ \text {s.t.:} & & & \\ & x + 2y + z \leq 430 \text{ (Constraint 1)}\\ & 3x + 2z \leq 460 \text{ (Constraint 2)} \\ & x + 4y \leq 420 \text{ (Constraint 3)} \\ & x, y, z \geq 0 \text{ (Non-negativity)} \\ \end{array}\right\} $$
In [2]:
sm = Tableau([-3, -2, -5])
sm.add_constraint([1, 2, 1], 430)
sm.add_constraint([3, 0, 2], 460)
sm.add_constraint([1, 4, 0], 420)
sm.is_fraction = True
sm.solve()
In [ ]: